package Leetcode;

public class mergeKLists {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }
    public ListNode merge(ListNode[] lists, int l, int r){
        if (l == r){
            return lists[l];
        }
        if (l > r){
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeList(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
    public ListNode mergeList(ListNode left, ListNode right) {
        if (left == null || right == null){
            return left != null ? left : right;
        }
        // 创建一个虚拟头节点作为合并后链表的起点
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy; // 当前合并链表的尾节点

        // 遍历两个链表，将较小的节点添加到合并链表中
        while (left != null && right != null) {
            if (left.val < right.val) {
                tail.next = left;
                left = left.next;
            } else {
                tail.next = right;
                right = right.next;
            }
            tail = tail.next; // 更新尾节点
        }

        // 如果仍有剩余节点，直接追加到合并链表的末尾
        if (left != null) {
            tail.next = left;
        } else {
            tail.next = right;
        }

        // 返回合并后的链表头节点
        return dummy.next;
    }
}
